package demo;

import java.util.*;

/**
 * 合并区间
 */
public class Solution41 {
	public int[][] merge(int[][] intervals) {
		if(intervals == null || intervals.length<=1) {
			return intervals;
		}
		List<int[]> list = new ArrayList<>();
		Arrays.sort(intervals, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		int i = 0, n = intervals.length;
		while (i < n) {
			int a = intervals[i][0];
			int b = intervals[i][1];
			while (i < n - 1 && b >= intervals[i + 1][0]) {
				b = Math.max(b, intervals[i + 1][1]);
				i++;
			}
			list.add(new int[] {a,b});
			i++;
		}
		return list.toArray(new int[list.size()][2]);
	}
}
